package niuke;

/**
 * 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
 */
public class MergeList {
    private ListNode headNode;

    public ListNode Merge(ListNode list1, ListNode list2) {
        this.headNode = list1;
        ListNode temp2 = list2;
        while (temp2 != null) {
            ListNode insertedNode = insert(list1, temp2.val);
            list1 = insertedNode;
            temp2 = temp2.next;
        }
        return headNode;
    }

    private ListNode insert(ListNode list, int val) {
        ListNode temp = list;
        ListNode newNode = new ListNode(val);
        if (temp.val >= val) {
            newNode.next = temp;
            this.headNode = newNode;
            return newNode;
        }
        ListNode preNode = null;
        while (temp != null) {
            if (temp.val < val) {
                preNode = temp;
                temp = temp.next;
            } else {
                preNode.next = newNode;
                newNode.next = temp;
                return newNode;
            }
        }
        preNode.next = newNode;
        return newNode;
    }

    private class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
}

